Using Java or C# Monitor for concurrency kernel
implies defensive multithreading programming

This read me file concerns the Java implementations


1. Introduction : read the associated paper which contains two families of examples

2. Process synchronization example: symmetrical rendez-vous paradigm. the chameneos paradigm

The synchronization example is the mutating chameneos paradigm [Kaiser 2003]. It involves a symmetrical rendez-vous before peer-to-peer cooperation of concurrent processes. The cooperation, depicted as a possible colour mutation between the chameneos of a pair, is not developed in this paper. Here we cope only with a solution where a chameneos eager to cooperate calls a rendez-vous server in order to find a partner.

3. Resource allocation example.

3.1. A new solution for a well known paradigm, the dining philosophers

The dining philosophers, originally posed by Dijkstra [Dijkstra 7I], is a paradigm for concurrent resource allocation. Five philosophers spend their life alternately thinking and eating. To dine, each philosopher sits around a circular table at a fixed place. In front of each philosopher is a plate of food, and between each pair of philosophers is a chopstick. In order to eat, a philosopher needs two chopsticks, and they agree that each will use only the chopsticks immediately to the left and to the right of his place. The problem is to write a program simulating the philosopher’s behaviours and to devise a protocol that avoids two unfortunate conclusions. In the first one, all philosophers are hungry but none is able to acquire both chopsticks since each holds one chopstick and refuses to give it up. This is deadlock, a safety concern. In the second one, a hungry philosopher will always lack one of the two chopsticks which are alternately used by its neighbours. This is starvation, a liveness consideration.
This paradigm has two well known approaches for obtaining a solution. In the first one, the chopsticks are allocated one by one, and a reliable solution is obtained by adding one of the usual constraints for deadlock prevention: the chopsticks are allocated in fixed (e.g., increasing) order; a chopstick allocation is denied as soon as the requested allocation would lead to an unsafe state (seated dinner, with only 4 chairs). Ada implementation of this approach can be found [Burns 1995, Barkaoui 1997]. In the second one, the chopsticks are allocated globally only, which is a safe solution; when a fair solution is necessary, it is obtained by adding reservation constraints, care being taken that these constraints do not reintroduce deadlock. Ada implementation are given in [Brosgol 1996, Kaiser 1997]
Let us consider now another approach which does not seem to have been much experimented except in [Kaiser 1997]. The chopsticks are allocated as many as available and the allocation is completed as soon as the missing chopsticks are released. Let us observe the behaviour of this solution when implemented in Java and in Ada and from these experiments, let us determine the conditions of its correctness.

3.2. Several Java implementations are provided

The implemented solutions stored in this repertory with a main environmental program are:
Thanks to Pascal Graffion for his help when compiling, executing and testing the Java programs.

3.3. The Resource example implementations have been coded in Ada and analysed by Quasar, our validation tool

The original solutions have been implemented in Ada  in order to  analyze them with  Quasar

The measured data are given in the full paper below

The data collected by Quasar are:
 The analysed implementations are:

a_UCHOP JAVA ADA (program and Quasar report)
b_RCHOP JAVA ADA (program and Quasar report)
c_RFCHOP JAVA ADA (program and Quasar report)
d_RCHOP ADA SINGLE (program and Quasar report)
e_NOTIFICATION JAVA ADA (program and Quasar report)
f_CONDITIONS JAVA ADA (program and Quasar report)
g_RCHOP ADA FAMILIES (program and Quasar report)
h_RCHOP JAVA GLOBAL (program and Quasar report)
i_PROGRAM SKELETON (program and Quasar report)

3.4.  The implementations have been simulated in Ada and instrumented
 
The different implementations have been instrumented for measuring concurrency effectiveness and collecting data:
The original solutions have been modified for allowing these measurements.
Several packages have been added :
The full Ada program is present in 1_CHOPCODE MONITORS  and is composed of:
chop.adb which is a dummy code which must be replaced by the experimented  one stored in another folder
chop.ads
diner.adb   which is the main program
global.adb
global.ads
monitoring.adb which contains the number of runs (MaxStrokes) and the individual messages (here replaced by null statement in procedure Message)
monitoring.ads
protected_machine.adb
protected_machine.ads

The main program is diner.adb
Once compiled (with GNAT for example), just run ./diner

The simulated implementations of the package chop.adb are in the following folders:
1_CHOPCODE MONITORS (programs skeleton)
b_RCHOP JAVA ADA
c_RFCHOP JAVA ADA
d_RCHOP ADA SINGLE
e_NOTIFICATION JAVA ADA
f_CONDITIONS JAVA ADA
g_RCHOP ADA FAMILIES
h_GLOBAL JAVA ADA

4. The full paper
Using Java or C# Monitor for concurrency kernel implies defensive multithreading programming
authors: Claude Kaiser, Jean-François Pradat-Peyre, Sami Évangelista, Pierre Rousseau

CEDRIC - CNAM Paris
292, rue St Martin, 75003 Paris
{kaiser, peyre, evangeli, rousseau}[at]cnam[dot]fr
http://quasar.cnam.fr/

It contains the data collected by Quasar and the data recorded by the simulations.

Last update: March 29, 2006